//===--- AliasAnalysis.h - PIL Alias Analysis -------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#ifndef POLARPHP_PIL_OPTIMIZER_ANALYSIS_ALIASANALYSIS_H
#define POLARPHP_PIL_OPTIMIZER_ANALYSIS_ALIASANALYSIS_H

#include "polarphp/basic/ValueEnumerator.h"
#include "polarphp/pil/lang/ApplySite.h"
#include "polarphp/pil/lang/PILInstruction.h"
#include "polarphp/pil/optimizer/analysis/Analysis.h"
#include "polarphp/pil/optimizer/analysis/SideEffectAnalysis.h"
#include "llvm/ADT/DenseMap.h"

using polar::RetainObserveKind;

namespace {

/// A key used for the AliasAnalysis cache.
///
/// This struct represents the argument list to the method 'alias'.  The two
/// PILValue pointers are mapped to size_t indices because we need an
/// efficient way to invalidate them (the mechanism is described below). The
/// Type arguments are translated to void* because their underlying storage is
/// opaque pointers that never goes away.
struct AliasKeyTy {
   // The PILValue pair:
   size_t V1, V2;
   // The TBAAType pair:
   void *T1, *T2;
};

/// A key used for the MemoryBehavior Analysis cache.
///
/// The two PILValue pointers are mapped to size_t indices because we need an
/// efficient way to invalidate them (the mechanism is described below).  The
/// RetainObserveKind represents the inspection mode for the memory behavior
/// analysis.
struct MemBehaviorKeyTy {
   // The PILValue pair:
   size_t V1, V2;
   RetainObserveKind InspectionMode;
};
}

namespace polar {

class PILInstruction;
class ValueBase;
class SideEffectAnalysis;
class EscapeAnalysis;

/// This class is a simple wrapper around an alias analysis cache. This is
/// needed since we do not have an "analysis" infrastructure.
class AliasAnalysis : public PILAnalysis {
public:

   /// This enum describes the different kinds of aliasing relations between
   /// pointers.
   ///
   /// NoAlias: There is never dependence between memory referenced by the two
   ///          pointers. Example: Two pointers pointing to non-overlapping
   ///          memory ranges.
   ///
   /// MayAlias: Two pointers might refer to the same memory location.
   ///
   ///
   /// PartialAlias: The two memory locations are known to be overlapping
   ///               but do not start at the same address.
   ///
   ///
   /// MustAlias: The two memory locations always start at exactly the same
   ///            location. The pointers are equal.
   ///
   enum class AliasResult : unsigned {
      NoAlias=0,      ///< The two values have no dependencies on each
      ///  other.
         MayAlias,       ///< The two values cannot be proven to alias or
      ///  not alias. Anything could happen.
         PartialAlias,   ///< The two values overlap in a partial manner.
      MustAlias,      ///< The two values are equal.
   };

private:
   PILModule *Mod;
   SideEffectAnalysis *SEA;
   EscapeAnalysis *EA;

   using TBAACacheKey = std::pair<PILType, PILType>;

   /// A cache for the computation of TBAA. True means that the types may
   /// alias. False means that the types must not alias.
   ///
   /// We don't need to invalidate this cache because type aliasing relations
   /// never change.
   llvm::DenseMap<TBAACacheKey, bool> TypesMayAliasCache;

   /// AliasAnalysis value cache.
   ///
   /// The alias() method uses this map to cache queries.
   llvm::DenseMap<AliasKeyTy, AliasResult> AliasCache;

   using MemoryBehavior = PILInstruction::MemoryBehavior;
   /// MemoryBehavior value cache.
   ///
   /// The computeMemoryBehavior() method uses this map to cache queries.
   llvm::DenseMap<MemBehaviorKeyTy, MemoryBehavior> MemoryBehaviorCache;

   /// The AliasAnalysis cache can't directly map a pair of ValueBase pointers
   /// to alias results because we'd like to be able to remove deleted pointers
   /// without having to scan the whole map. So, instead of storing pointers we
   /// map pointers to indices and store the indices.
   ValueEnumerator<ValueBase*> AliasValueBaseToIndex;

   /// Same as AliasValueBaseToIndex, map a pointer to the indices for
   /// MemoryBehaviorCache.
   ///
   /// NOTE: we do not use the same ValueEnumerator for the alias cache,
   /// as when either cache is cleared, we can not clear the ValueEnumerator
   /// because doing so could give rise to collisions in the other cache.
   ValueEnumerator<PILNode*> MemoryBehaviorNodeToIndex;

   AliasResult aliasAddressProjection(PILValue V1, PILValue V2,
                                      PILValue O1, PILValue O2);

   /// Perform an alias query to see if V1, V2 refer to the same values.
   AliasResult aliasInner(PILValue V1, PILValue V2,
                          PILType TBAAType1 = PILType(),
                          PILType TBAAType2 = PILType());

   /// Returns True if memory of type \p T1 and \p T2 may alias.
   bool typesMayAlias(PILType T1, PILType T2, const PILFunction &F);

   virtual void handleDeleteNotification(PILNode *node) override {
      assert(node->isRepresentativePILNodeInObject());

      // The pointer 'node' is going away.  We can't scan the whole cache
      // and remove all of the occurrences of the pointer. Instead we remove
      // the pointer from the cache that translates pointers to indices.
      auto value = dyn_cast<ValueBase>(node);
      if (!value) return;

      AliasValueBaseToIndex.invalidateValue(value);
      MemoryBehaviorNodeToIndex.invalidateValue(node);
   }

   virtual bool needsNotifications() override { return true; }


public:
   AliasAnalysis(PILModule *M)
      : PILAnalysis(PILAnalysisKind::Alias), Mod(M), SEA(nullptr), EA(nullptr) {
   }

   static bool classof(const PILAnalysis *S) {
      return S->getKind() == PILAnalysisKind::Alias;
   }

   virtual void initialize(PILPassManager *PM) override;

   /// Perform an alias query to see if V1, V2 refer to the same values.
   AliasResult alias(PILValue V1, PILValue V2, PILType TBAAType1 = PILType(),
                     PILType TBAAType2 = PILType());

   /// Convenience method that returns true if V1 and V2 must alias.
   bool isMustAlias(PILValue V1, PILValue V2, PILType TBAAType1 = PILType(),
                    PILType TBAAType2 = PILType()) {
      return alias(V1, V2, TBAAType1, TBAAType2) == AliasResult::MustAlias;
   }

   /// Convenience method that returns true if V1 and V2 partially alias.
   bool isPartialAlias(PILValue V1, PILValue V2, PILType TBAAType1 = PILType(),
                       PILType TBAAType2 = PILType()) {
      return alias(V1, V2, TBAAType1, TBAAType2) == AliasResult::PartialAlias;
   }

   /// Convenience method that returns true if V1, V2 cannot alias.
   bool isNoAlias(PILValue V1, PILValue V2, PILType TBAAType1 = PILType(),
                  PILType TBAAType2 = PILType()) {
      return alias(V1, V2, TBAAType1, TBAAType2) == AliasResult::NoAlias;
   }

   /// Convenience method that returns true if V1, V2 may alias.
   bool isMayAlias(PILValue V1, PILValue V2, PILType TBAAType1 = PILType(),
                   PILType TBAAType2 = PILType()) {
      return alias(V1, V2, TBAAType1, TBAAType2) == AliasResult::MayAlias;
   }

   /// \returns True if the release of the \p Ptr can access memory accessed by
   /// \p User.
   bool mayValueReleaseInterfereWithInstruction(PILInstruction *User,
                                                PILValue Ptr);

   /// Use the alias analysis to determine the memory behavior of Inst with
   /// respect to V.
   ///
   /// TODO: When ref count behavior is separated from generic memory behavior,
   /// the InspectionMode flag will be unnecessary.
   MemoryBehavior computeMemoryBehavior(PILInstruction *Inst, PILValue V,
                                        RetainObserveKind);

   /// Use the alias analysis to determine the memory behavior of Inst with
   /// respect to V.
   ///
   /// TODO: When ref count behavior is separated from generic memory behavior,
   /// the InspectionMode flag will be unnecessary.
   MemoryBehavior computeMemoryBehaviorInner(PILInstruction *Inst, PILValue V,
                                             RetainObserveKind);

   /// Returns true if \p Inst may read from memory in a manner that
   /// affects V.
   bool mayReadFromMemory(PILInstruction *Inst, PILValue V) {
      auto B = computeMemoryBehavior(Inst, V, RetainObserveKind::IgnoreRetains);
      return B == MemoryBehavior::MayRead ||
             B == MemoryBehavior::MayReadWrite ||
             B == MemoryBehavior::MayHaveSideEffects;
   }

   /// Returns true if \p Inst may write to memory in a manner that
   /// affects V.
   bool mayWriteToMemory(PILInstruction *Inst, PILValue V) {
      auto B = computeMemoryBehavior(Inst, V, RetainObserveKind::IgnoreRetains);
      return B == MemoryBehavior::MayWrite ||
             B == MemoryBehavior::MayReadWrite ||
             B == MemoryBehavior::MayHaveSideEffects;
   }

   /// Returns true if \p Inst may read or write to memory in a manner that
   /// affects V.
   bool mayReadOrWriteMemory(PILInstruction *Inst, PILValue V) {
      auto B = computeMemoryBehavior(Inst, V, RetainObserveKind::IgnoreRetains);
      return MemoryBehavior::None != B;
   }

   /// Returns true if Inst may have side effects in a manner that affects V.
   bool mayHaveSideEffects(PILInstruction *Inst, PILValue V) {
      auto B = computeMemoryBehavior(Inst, V, RetainObserveKind::ObserveRetains);
      return B == MemoryBehavior::MayWrite ||
             B == MemoryBehavior::MayReadWrite ||
             B == MemoryBehavior::MayHaveSideEffects;
   }

   /// Returns true if Inst may have side effects in a manner that affects
   /// V. This is independent of whether or not Inst may write to V and is meant
   /// to encode notions such as ref count modifications.
   bool mayHavePureSideEffects(PILInstruction *Inst, PILValue V) {
      auto B = computeMemoryBehavior(Inst, V, RetainObserveKind::ObserveRetains);
      return MemoryBehavior::MayHaveSideEffects == B;
   }

   /// Returns true if \p Ptr may be released in the function call \p FAS.
   bool canApplyDecrementRefCount(FullApplySite FAS, PILValue Ptr);

   /// Returns true if \p Ptr may be released by the builtin \p BI.
   bool canBuiltinDecrementRefCount(BuiltinInst *BI, PILValue Ptr);

   /// Encodes the alias query as a AliasKeyTy.
   /// The parameters to this function are identical to the parameters of alias()
   /// and this method serializes them into a key for the alias analysis cache.
   AliasKeyTy toAliasKey(PILValue V1, PILValue V2, PILType Type1, PILType Type2);

   /// Encodes the memory behavior query as a MemBehaviorKeyTy.
   MemBehaviorKeyTy toMemoryBehaviorKey(PILInstruction *V1, PILValue V2,
                                        RetainObserveKind K);

   virtual void invalidate() override {
      AliasCache.clear();
      MemoryBehaviorCache.clear();
   }

   virtual void invalidate(PILFunction *,
                           PILAnalysis::InvalidationKind K) override {
      invalidate();
   }

   /// Notify the analysis about a newly created function.
   virtual void notifyAddedOrModifiedFunction(PILFunction *F) override {}

   /// Notify the analysis about a function which will be deleted from the
   /// module.
   virtual void notifyWillDeleteFunction(PILFunction *F) override {}

   virtual void invalidateFunctionTables() override { }
};


llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
                              AliasAnalysis::AliasResult R);

/// If this value is an address that obeys strict TBAA, return the address type.
/// Otherwise, return an empty type.
PILType computeTBAAType(PILValue V);

/// Check if \p V points to a let-member.
/// Nobody can write into let members.
bool isLetPointer(PILValue V);

} // end namespace polar

namespace llvm {
template <> struct DenseMapInfo<AliasKeyTy> {
   static inline AliasKeyTy getEmptyKey() {
      auto Allone = std::numeric_limits<size_t>::max();
      return {0, Allone, nullptr, nullptr};
   }
   static inline AliasKeyTy getTombstoneKey() {
      auto Allone = std::numeric_limits<size_t>::max();
      return {Allone, 0, nullptr, nullptr};
   }
   static unsigned getHashValue(const AliasKeyTy Val) {
      unsigned H = 0;
      H ^= DenseMapInfo<size_t>::getHashValue(Val.V1);
      H ^= DenseMapInfo<size_t>::getHashValue(Val.V2);
      H ^= DenseMapInfo<void *>::getHashValue(Val.T1);
      H ^= DenseMapInfo<void *>::getHashValue(Val.T2);
      return H;
   }
   static bool isEqual(const AliasKeyTy LHS, const AliasKeyTy RHS) {
      return LHS.V1 == RHS.V1 &&
             LHS.V2 == RHS.V2 &&
             LHS.T1 == RHS.T1 &&
             LHS.T2 == RHS.T2;
   }
};

template <> struct DenseMapInfo<MemBehaviorKeyTy> {
   static inline MemBehaviorKeyTy getEmptyKey() {
      auto Allone = std::numeric_limits<size_t>::max();
      return {0, Allone, RetainObserveKind::RetainObserveKindEnd};
   }
   static inline MemBehaviorKeyTy getTombstoneKey() {
      auto Allone = std::numeric_limits<size_t>::max();
      return {Allone, 0, RetainObserveKind::RetainObserveKindEnd};
   }
   static unsigned getHashValue(const MemBehaviorKeyTy V) {
      unsigned H = 0;
      H ^= DenseMapInfo<size_t>::getHashValue(V.V1);
      H ^= DenseMapInfo<size_t>::getHashValue(V.V2);
      H ^= DenseMapInfo<int>::getHashValue(static_cast<int>(V.InspectionMode));
      return H;
   }
   static bool isEqual(const MemBehaviorKeyTy LHS,
                       const MemBehaviorKeyTy RHS) {
      return LHS.V1 == RHS.V1 &&
             LHS.V2 == RHS.V2 &&
             LHS.InspectionMode == RHS.InspectionMode;
   }
};
} // llvm

#endif
